/*
 * @Author: 0x9DEFA478
 * @Date: 2025-08-24 21:07:54
 * @LastEditTime: 2025-10-18 00:15:23
 * @LastEditors: 0x9DEFA478
 * @Description: 
 * 
 */
#ifndef hTree_H_Tree_HPP_
#define hTree_H_Tree_HPP_
#include "./H_Tree.h"
#include "../H_Pointer.hpp"
#include "../Container/H_Stack.hpp"
#include "../Utility/H_Trait.hpp"
#include "../Utility/H_Concept.hpp"
#include <type_traits>
#if __cplusplus >= 202000L
#include <concepts>
#endif
#if defined(cH_Assert_TreeMerge)&&(cH_Assert_TreeMerge!=0)
#include <stdexcept>
#include "SystemUtility/C_iostream.hpp"
#endif


namespace H{

  namespace Tree{

    namespace Internal{

      enum class FindInsertResult:int{
        InsertToLeft=vH_Tree_FindInsert_Result_InsertToLeft,
        InsertToRight=vH_Tree_FindInsert_Result_InsertToRight,
        InsertToRoot=vH_Tree_FindInsert_Result_InsertToRoot,
        Exist=vH_Tree_FindInsert_Result_Exist
      };

      struct TypeCompare_Less{
        template<typename TypeKey>
        int operator()(const TypeKey& x,const TypeKey& y)const noexcept{
          if(x<y){
            return -1;
          }
          if(y<x){
            return 1;
          }
          return 0;
        }
      };

#if __cplusplus >= 202000L
      struct TypeCompare{
        template<H::Concept::const_compare TypeKey>
        int operator()(const TypeKey& x,const TypeKey& y)const noexcept{return x.compare(y);}
        template<typename TypeKey>
        requires (!H::Concept::const_compare<TypeKey>)
        int operator()(const TypeKey& x,const TypeKey& y)const noexcept{
          if(x<y){
            return -1;
          }
          if(y<x){
            return 1;
          }
          return 0;
        }
      };
#else
      struct TypeCompare{
        template<typename TypeKey>
        std::enable_if_t<Trait::is_const_compare<TypeKey>::value,int> operator()(const TypeKey& x,const TypeKey& y)const noexcept{return x.compare(y);}
        template<typename TypeKey>
        std::enable_if_t<!Trait::is_const_compare<TypeKey>::value,int> operator()(const TypeKey& x,const TypeKey& y)const noexcept{
          if(x<y){
            return -1;
          }
          if(y<x){
            return 1;
          }
          return 0;
        }
      };
#endif

      template<typename TypeLL,typename TypeKey,typename TypeData>
      struct NodeBase:TypeLL{

        static constexpr std::size_t MaxAlign()noexcept{return Max(alignof(NodeBase),Max(alignof(TypeKey),alignof(TypeData)));}
        static constexpr std::size_t KeyOffset(){return IncreaseAlignTo(sizeof(NodeBase),alignof(TypeKey));}
        static constexpr std::size_t DataOffset()noexcept{return IncreaseAlignTo(KeyOffset()+sizeof(TypeKey),alignof(TypeData));}
        static constexpr std::size_t DataSize()noexcept{return sizeof(TypeData);}
        static constexpr std::size_t Size()noexcept{return IncreaseAlignTo(DataOffset()+DataSize(),MaxAlign());}

        static TypeLL* CastKey(TypeKey* key)noexcept{
          return reinterpret_cast<TypeLL*>(reinterpret_cast<byte*>(key)-KeyOffset());
        }
        static const TypeLL* CastKey(const TypeKey* key)noexcept{
          return reinterpret_cast<const TypeLL*>(reinterpret_cast<const byte*>(key)-KeyOffset());
        }

        static TypeLL* CastData(TypeData* data)noexcept{
          return reinterpret_cast<TypeLL*>(reinterpret_cast<byte*>(data)-DataOffset());
        }
        static const TypeLL* CastData(const TypeData* data)noexcept{
          return reinterpret_cast<const TypeLL*>(reinterpret_cast<const byte*>(data)-DataOffset());
        }

        static TypeKey* ToKey(TypeLL* ll_node)noexcept{
          return reinterpret_cast<TypeKey*>(reinterpret_cast<byte*>(ll_node)+KeyOffset());
        }
        static const TypeKey* ToKey(const TypeLL* ll_node)noexcept{
          return reinterpret_cast<const TypeKey*>(reinterpret_cast<const byte*>(ll_node)+KeyOffset());
        }

        static TypeData* ToData(TypeLL* ll_node)noexcept{
          return reinterpret_cast<TypeData*>(reinterpret_cast<byte*>(ll_node)+DataOffset());
        }
        static const TypeData* ToData(const TypeLL* ll_node)noexcept{
          return reinterpret_cast<const TypeData*>(reinterpret_cast<const byte*>(ll_node)+DataOffset());
        }

      };

#if __cplusplus >= 202000L
      namespace Concept{
        
        template<typename T,typename TypeKey>
        concept TypeCompare=requires(T compare,const TypeKey& key){
          static_cast<int>(compare(key,key));
        };

        template<typename T,typename TypeLL,typename TypeKey,typename TypeData>
        concept tree_interface=requires(TypeLL* ll_p,NodeBase<TypeLL,TypeKey,TypeData>* tree
          ,const TypeKey& key_c
          ,FindInsertResult findInsertResult)
        {
          {T::FirstFree(tree)}->std::same_as<TypeLL*>;
          {T::NextFree(ll_p)}->std::same_as<TypeLL*>;
          {T::FindInsert(tree,key_c,&ll_p)}->std::same_as<FindInsertResult>;
          T::InsertTo(&tree,ll_p,ll_p,findInsertResult);
          T::Remove(&tree,ll_p);
          {T::Find(tree,key_c)}->std::same_as<TypeLL*>;
          {T::FrontNode(tree)}->std::same_as<TypeLL*>;
          {T::BackNode(tree)}->std::same_as<TypeLL*>;
          {T::Node_Forward(ll_p)}->std::same_as<TypeLL*>;
          {T::Node_Backward(ll_p)}->std::same_as<TypeLL*>;
          T::Node_Copy(ll_p,ll_p);
          {T::Node_Left(ll_p)}->std::same_as<TypeLL*>;
          {T::Node_Right(ll_p)}->std::same_as<TypeLL*>;
          T::Node_SetLeft(ll_p,ll_p);
          T::Node_SetRight(ll_p,ll_p);
        };
      }
#endif

      /**
       * @brief 树的底层抽象模板类
       *        模板参数为底层树的类型与操作函数
       *        管理节点的分配与访问
       * @param TypeLL 底层节点类型
       * @param TypeKey Key类型
       * @param TypeData Data类型
       * @param Allocator 分配器类型
       * @param TreeInterface 树的底层接口
       */
      template<typename TypeLL,typename TypeKey,typename TypeData
#if __cplusplus >= 202000L
        ,H::Concept::allocator Allocator
        ,Concept::tree_interface<TypeLL,TypeKey,TypeData> TreeInterface
#else
        ,typename Allocator
        ,typename TreeInterface
#endif
      >
      class TreeLL{
#if __cplusplus < 202000L
        static_assert(is_allocator_v<Allocator>);
#endif

        public:
          using Node=NodeBase<TypeLL,TypeKey,TypeData>;

          struct InsertResult{
            TypeLL* ll_node;
            bool ok;
          };

        private:
          using NodePool=Pool::ObjectInert<Allocator,Node::Size()>;

        private:

          static TypeLL* AllocNode(NodePool* nodePool){
            TypeLL* r;
            void* memory=nodePool->Alloc();

            try{
              r=new(static_cast<TypeLL*>(memory))TypeLL();
            }catch(...){
              NodePool::Dealloc(memory);
            }

            return r;
          }

          static void FreeNode(NodePool* nodePool,TypeLL* ll_node)noexcept{
            ll_node->~TypeLL();
            nodePool->Free(static_cast<void*>(ll_node));
          }

          template<typename T,typename... T_Arg>
          static TypeLL* NewNode(NodePool* nodePool,T&& Key,T_Arg&&... Args){
            TypeLL* r;
            TypeKey* key;

            r=nullptr;
            key=nullptr;
            try{
              r=AllocNode(nodePool);
              key=new(Node::ToKey(r))TypeKey(std::forward<T>(Key));
              new(Node::ToData(r))TypeData(std::forward<T_Arg>(Args)...);
            }catch(...){
              if(key!=nullptr){
                Node::ToKey(r)->~TypeKey();
              }
              if(r!=nullptr){
                FreeNode(nodePool,r);
                nodePool->Trim();
              }
              throw;
            }

            return r;
          }

          static TypeLL* CopyNewNode(NodePool* nodePool,const TypeLL* srcNode){
            TypeLL* r;
            TypeKey* key;

            r=nullptr;
            key=nullptr;
            try{
              r=AllocNode(nodePool);
              key=new(Node::ToKey(r))TypeKey(*Node::ToKey(srcNode));
              new(Node::ToData(r))TypeData(*Node::ToData(srcNode));
            }catch(...){
              if(key!=nullptr){
                Node::ToKey(r)->~TypeKey();
              }
              if(r!=nullptr){
                FreeNode(nodePool,r);
                nodePool->Trim();
              }
              throw;
            }

            return r;
          }

          static void DeleteNode(NodePool* nodePool,TypeLL* ll_node)noexcept{
            Node::ToData(ll_node)->~TypeData();
            Node::ToKey(ll_node)->~TypeKey();
            FreeNode(nodePool,ll_node);
          }

          static void DeallocNode(TypeLL* ll_node)noexcept{
            Node::ToData(ll_node)->~TypeData();
            Node::ToKey(ll_node)->~TypeKey();
            ll_node->~TypeLL();
            NodePool::Dealloc(static_cast<void*>(ll_node));
          }

          TypeLL* CopyTree(NodePool* nodePool)const{
            enum class eFindType{
              None,
              Left,
              Right
            };

            struct StackItem{
              TypeLL* SrcNode;
              TypeLL* DstNode;
              TypeLL* ResNode;

              eFindType FindType;

              StackItem(const StackItem&)=default;

              StackItem(TypeLL* SrcNode):SrcNode(SrcNode),DstNode(nullptr),ResNode(nullptr),FindType(eFindType::None){}
            };

            if(tree==nullptr){
              return nullptr;
            }

            H::Stack<StackItem,Allocator> stack;
            H::Stack<TypeLL*,Allocator> stack_node;
            StackItem currentStatus(tree);

            try{
              for(;;){

                if(currentStatus.FindType==eFindType::None){
                  auto node=CopyNewNode(nodePool,currentStatus.SrcNode);
                  stack_node.Push(node);
                  TreeInterface::Node_Copy(node,currentStatus.SrcNode);
                  currentStatus.DstNode=node;

                  currentStatus.FindType=eFindType::Left;
                  auto SrcLeft=TreeInterface::Node_Left(currentStatus.SrcNode);
                  if(SrcLeft!=nullptr){
                    stack.Push(currentStatus);
                    currentStatus=SrcLeft;
                    continue;
                  }else{
                    currentStatus.ResNode=nullptr;
                  }
                }
                
                if(currentStatus.FindType==eFindType::Left){

                  TreeInterface::Node_SetLeft(currentStatus.DstNode,currentStatus.ResNode);

                  currentStatus.FindType=eFindType::Right;
                  auto SrcRight=TreeInterface::Node_Right(currentStatus.SrcNode);
                  if(SrcRight!=nullptr){
                    stack.Push(currentStatus);
                    currentStatus=SrcRight;
                    continue;
                  }else{
                    currentStatus.ResNode=nullptr;
                  }
                }

                TreeInterface::Node_SetRight(currentStatus.DstNode,currentStatus.ResNode);

                if(stack.Empty()){
                  break;
                }
                stack.Top().ResNode=currentStatus.DstNode;
                currentStatus=stack.Top();
                stack.Pop();
              }
            }catch(...){
              for(auto& Item:stack_node){
                DeallocNode(Item);
              }
              throw;
            }

            return currentStatus.DstNode;
          }

        public:

          void ClearAll()noexcept{

            if(tree==nullptr){
              return;
            }

            auto root=static_cast<TypeLL*>(tree);
            auto rp=TreeInterface::FirstFree(tree);

            for(;;){
              auto L=TreeInterface::Node_Left(rp);
              auto R=TreeInterface::Node_Right(rp);

              if(L!=nullptr){
                DeleteNode(&nodePool,L);
              }
              if(R!=nullptr){
                DeleteNode(&nodePool,R);
              }

              if(rp==root){
                DeleteNode(&nodePool,rp);
                break;
              }
              
              rp=TreeInterface::NextFree(rp);
            }

            tree=nullptr;
          }

        public:
          explicit TreeLL()noexcept:tree(nullptr),count(0){}

          TreeLL(const TreeLL& treeLL)noexcept:count(treeLL.count){tree=static_cast<Node*>(treeLL.CopyTree(&nodePool));}
          TreeLL(TreeLL&& treeLL)noexcept:tree(treeLL.tree),nodePool(std::move(treeLL.nodePool)),count(treeLL.count){
            treeLL.tree=nullptr;
            treeLL.count=0;
          }
          TreeLL& operator=(const TreeLL& treeLL)noexcept{
            if(this==&treeLL){
              return* this;
            }
            auto newTree=static_cast<Node*>(treeLL.CopyTree(&nodePool));
            ClearAll();
            tree=newTree;
            count=treeLL.count;
            return *this;
          }
          TreeLL& operator=(TreeLL&& treeLL)noexcept{
            if(this==&treeLL){
              return* this;
            }
            ClearAll();
            nodePool=std::move(treeLL.nodePool);
            tree=treeLL.tree;
            count=treeLL.count;
            treeLL.tree=nullptr;
            treeLL.count=0;
            return *this;
          }

          ~TreeLL()noexcept{ClearAll();}

          void Trim()noexcept{nodePool.Trim();}
          usize Count()const noexcept{return count;}
          usize Empty()const noexcept{return tree==nullptr;}

          TypeLL* FindNode(const TypeKey& Key)const noexcept{
            return TreeInterface::Find(tree,Key);
          }

          TypeLL* ForwardBegin()const noexcept{
            return TreeInterface::FrontNode(tree);
          }

          TypeLL* BackwardBegin()const noexcept{
            return TreeInterface::BackNode(tree);
          }

          static TypeLL* NodeForward(TypeLL* node)noexcept{
            return TreeInterface::Node_Forward(node);
          }

          static TypeLL* NodeBackward(TypeLL* node)noexcept{
            return TreeInterface::Node_Backward(node);
          }

          Pointer<TypeLL> Remove(const TypeKey& Key)noexcept{
            auto ll_node=FindNode(Key);
            if(ll_node==nullptr){
              return Pointer<TypeLL>();
            }

            count--;
            TreeInterface::Remove(&tree,ll_node);
            return Pointer<TypeLL>(ll_node,DeallocNode);
          }

          bool Erase(const TypeKey& Key)noexcept{
            auto ll_node=FindNode(Key);
            if(ll_node==nullptr){
              return false;
            }

            count--;
            TreeInterface::Remove(&tree,ll_node);
            DeleteNode(&nodePool,ll_node);
            return true;
          }

          template<typename T,typename... T_Arg>
          InsertResult Insert(T&& Key,T_Arg&&... Args){
            TypeLL* ReturnNode;
            auto FindInsert_Result=TreeInterface::FindInsert(tree,Key,&ReturnNode);
            if(FindInsert_Result==FindInsertResult::Exist){
              return {ReturnNode,false};
            }

            count++;
            auto newNode=NewNode(&nodePool,std::forward<T>(Key),std::forward<T_Arg>(Args)...);
            TreeInterface::InsertTo(&tree,newNode,ReturnNode,FindInsert_Result);
            return {newNode,true};
          }

        private:
          TypeLL* InsertNode(TypeLL* ll_node)noexcept{
            TypeLL* ReturnNode;
            auto FindInsert_Result=TreeInterface::FindInsert(tree,*Node::ToKey(ll_node),&ReturnNode);
            if(FindInsert_Result==FindInsertResult::Exist){
              return ReturnNode;
            }

            count++;
            TreeInterface::InsertTo(&tree,ll_node,ReturnNode,FindInsert_Result);
            return ll_node;
          }

        public:

          void Merge(TreeLL& treeLL)noexcept{

            struct StackItem{
              TypeLL* node;
              TypeLL* left;
              TypeLL* right;

              StackItem(const StackItem&)=default;

              StackItem(TypeLL* ll_node):node(ll_node),left(TreeInterface::Node_Left(ll_node)),right(TreeInterface::Node_Right(ll_node)){}
            };

            if(treeLL.tree==nullptr){
              return;
            }

            H::Stack<StackItem,Allocator> stack;
            StackItem currentStatus(treeLL.tree);

            treeLL.tree=nullptr;
            treeLL.count=0;

            for(;;){
              auto ll_node=currentStatus.node;

              if(ll_node!=nullptr){
                currentStatus.node=nullptr;

                auto res_node=InsertNode(ll_node);

                if(res_node!=ll_node){
#if defined(cH_Assert_TreeMerge)&&(cH_Assert_TreeMerge!=0)
                  if(ll_node!=treeLL.InsertNode(ll_node)){
                    H::cerr<<"H::Tree::Internal::TreeLL发现树的行为异常"<<std::endl;
                    std::terminate();
                  }
#else
                  treeLL.InsertNode(ll_node);
#endif
                }
              }

              ll_node=currentStatus.left;
              if(ll_node!=nullptr){
                currentStatus.left=nullptr;

                stack.Push(currentStatus);
                currentStatus=ll_node;
                continue;
              }

              ll_node=currentStatus.right;
              if(ll_node!=nullptr){
                currentStatus.right=nullptr;

                stack.Push(currentStatus);
                currentStatus=ll_node;
                continue;
              }

              if(stack.Empty()){
                break;
              }
              currentStatus=stack.Top();
              stack.Pop();
            }

          }

        private:
          Node* tree;
          NodePool nodePool;
          usize count;
      };

      /**
       * @brief 树的抽象模板类
       *        树的操作接口实现
       * @param TypeLL 底层节点类型
       * @param TypeKey Key类型
       * @param TypeData Data类型
       * @param Allocator 分配器类型
       * @param TreeInterface 树的底层接口
       */
      template<typename TypeLL,typename TypeKey,typename TypeData
#if __cplusplus >= 202000L
        ,H::Concept::allocator Allocator
        ,Concept::tree_interface<TypeLL,TypeKey,TypeData> TreeInterface
#else
        ,typename Allocator
        ,typename TreeInterface
#endif
      >
      class TreeBase{
        static_assert(std::is_destructible_v<TypeKey>);
        static_assert(!std::is_void_v<TypeKey>);
        static_assert(!std::is_void_v<TypeData>);
        static_assert(!std::is_const_v<TypeKey>);
        static_assert(!std::is_const_v<TypeData>);
        static_assert(!std::is_volatile_v<TypeKey>);
        static_assert(!std::is_volatile_v<TypeData>);
#if __cplusplus < 202000L
        static_assert(is_allocator_v<Allocator>);
#endif

        private:
          using Node=NodeBase<TypeLL,TypeKey,TypeData>;
          
          using Tree=TreeLL<TypeLL,TypeKey,TypeData
            ,Allocator
            ,TreeInterface
          >;

        public:

          struct initializer_list_item{
            TypeKey key;
            TypeData data;
          };

          class RemoveResult{
            private:
              explicit RemoveResult(const Pointer<TypeLL>& Pointer)noexcept:pointer(Pointer){}
              explicit RemoveResult(Pointer<TypeLL>&& Pointer)noexcept:pointer(std::move(Pointer)){}

              friend class TreeBase;
            public:
              ~RemoveResult()noexcept=default;

              RemoveResult(const RemoveResult& removeResult)noexcept:pointer(removeResult.pointer){}
              RemoveResult(RemoveResult&& removeResult)noexcept:pointer(std::move(removeResult.pointer)){}

              RemoveResult& operator=(const RemoveResult& removeResult)noexcept{pointer=removeResult.pointer;return *this;}
              RemoveResult& operator=(RemoveResult&& removeResult)noexcept{pointer=std::move(removeResult.pointer);return *this;};

              operator bool()const noexcept{return pointer!=nullptr;}
              bool Valid()const noexcept{return pointer!=nullptr;}

              const TypeKey& Key()const noexcept{return *Node::ToKey(pointer.GetPointer());}

              const TypeData& Data()const noexcept{return *Node::ToData(pointer.GetPointer());}
              TypeData& Data()noexcept{return *Node::ToData(pointer.GetPointer());}
            private:
              Pointer<TypeLL> pointer;
          };

          template<typename T>
          class IteratorBase;

          template<typename T>
          class Reverse_IteratorBase;

          class Item{
            private:
              explicit Item(TypeLL* ll_node)noexcept:ll_node(ll_node){}

              TypeLL* NodePointer()noexcept{return ll_node;}

              Item& operator=(TypeLL* ll_node){this->ll_node=ll_node;return *this;}

              friend class IteratorBase<Item>;
              friend class IteratorBase<const Item>;
              friend class Reverse_IteratorBase<Item>;
              friend class Reverse_IteratorBase<const Item>;
            public:
              Item(const Item&)noexcept=default;

              Item& operator=(const Item&)noexcept=default;

              bool operator==(const Item& item)const noexcept{return ll_node==item.ll_node;}
              bool operator!=(const Item& item)const noexcept{return ll_node!=item.ll_node;}

              ~Item()noexcept=default;

              const TypeKey& Key()const noexcept{return *Node::ToKey(ll_node);}

              const TypeData& Data()const noexcept{return *Node::ToData(ll_node);}
              TypeData& Data()noexcept{return *Node::ToData(ll_node);}

            private:
              TypeLL* ll_node;
          };

          template<typename T>
          class IteratorBase{
            protected:
              explicit IteratorBase(TypeLL* ll_node)noexcept:item(ll_node){};

              void NodeForward()noexcept{
                item=Tree::NodeForward(item.NodePointer());
              }

              void NodeBackward()noexcept{
                item=Tree::NodeBackward(item.NodePointer());
              }

              friend class TreeBase;
            public:
              IteratorBase()noexcept:item(nullptr){}
              ~IteratorBase()noexcept=default;
            
              IteratorBase(const IteratorBase&)noexcept=default;

              IteratorBase& operator=(const IteratorBase&)=default;

              const T* GetPointer()const noexcept{return &item;}
              T* GetPointer()noexcept{return &item;}
              const T* operator->()const noexcept{return &item;}
              T* operator->()noexcept{return &item;}

              const T& operator*()const noexcept{return item;}
              T& operator*()noexcept{return item;}

              IteratorBase operator++(int)noexcept{IteratorBase r(item.NodePointer());NodeForward();return r;}
              IteratorBase& operator++()noexcept{NodeForward();return *this;}
              IteratorBase operator--(int)noexcept{IteratorBase r(item.NodePointer());NodeBackward();return r;}
              IteratorBase& operator--()noexcept{NodeBackward();return *this;}

#if __cplusplus >= 202000L
              template<typename T_I>
              requires std::same_as<std::remove_cv_t<T>,std::remove_cv_t<T_I>>
              bool operator==(const IteratorBase<T_I>& iterator)const noexcept{return this->item==*iterator;}
              template<typename T_I>
              requires std::same_as<std::remove_cv_t<T>,std::remove_cv_t<T_I>>
              bool operator!=(const IteratorBase<T_I>& iterator)const noexcept{return this->item!=*iterator;}
#else
              template<typename T_I>
              std::enable_if_t<std::is_same_v<std::remove_cv_t<T>,std::remove_cv_t<T_I>>,bool> operator==(const IteratorBase<T_I>& iterator)const noexcept{return this->item==*iterator;}
              template<typename T_I>
              std::enable_if_t<std::is_same_v<std::remove_cv_t<T>,std::remove_cv_t<T_I>>,bool> operator!=(const IteratorBase<T_I>& iterator)const noexcept{return this->item!=*iterator;}
#endif
            protected:
              Item item;
          };

          template<typename T>
          class Reverse_IteratorBase:public IteratorBase<T>{
            protected:
              explicit Reverse_IteratorBase(TypeLL* ll_node)noexcept:Reverse_IteratorBase::IteratorBase(ll_node){};

              friend class TreeBase;
            public:
              Reverse_IteratorBase()noexcept{}
              ~Reverse_IteratorBase()noexcept=default;
            
              Reverse_IteratorBase(const Reverse_IteratorBase&)noexcept=default;

              Reverse_IteratorBase& operator=(const Reverse_IteratorBase&)=default;

              Reverse_IteratorBase operator++(int)noexcept{Reverse_IteratorBase r(this->item.NodePointer());this->NodeBackward();return r;}
              Reverse_IteratorBase& operator++()noexcept{this->NodeBackward();return *this;}
              Reverse_IteratorBase operator--(int)noexcept{Reverse_IteratorBase r(this->item.NodePointer());this->NodeForward();return r;}
              Reverse_IteratorBase& operator--()noexcept{this->NodeForward();return *this;}

          };

          using Iterator=IteratorBase<Item>;
          using ConstIterator=IteratorBase<const Item>;
          using Reverse_Iterator=Reverse_IteratorBase<Item>;
          using Reverse_ConstIterator=Reverse_IteratorBase<const Item>;

          struct InsertResult{
            Iterator iterator;
            bool ok;
          };

        public:

          TreeBase()noexcept=default;

          TreeBase(std::initializer_list<initializer_list_item>& initializer_list){
            for(auto& Item:initializer_list){
              tree.Insert(Item.key,Item.data);
            }
          }

          TreeBase(std::initializer_list<initializer_list_item>&& initializer_list):TreeBase(initializer_list){}

          TreeBase(const TreeBase&)=default;
          TreeBase(TreeBase&&)noexcept=default;

          TreeBase& operator=(const TreeBase& treeBase){
            tree=treeBase.tree;
            return *this;
          }
          
          TreeBase& operator=(TreeBase&& treeBase)noexcept{
            tree=std::move(treeBase.tree);
            return *this;
          }

          ~TreeBase()noexcept=default;

          void Trim(){tree.Trim();}
          usize Count()const noexcept{return tree.Count();}
          usize Empty()const noexcept{return tree.Empty();}

        private:
          static InsertResult MakeInsertResult(TypeLL* ll_node,bool IsOk)noexcept{
            return {Iterator(ll_node),IsOk};
          }
          
        public:
          template<typename... T_Arg>
          InsertResult Insert(const TypeKey& Key,T_Arg&&... Args){
            auto res=tree.Insert(Key,std::forward<T_Arg>(Args)...);
            return MakeInsertResult(res.ll_node,res.ok);
          }
          template<typename... T_Arg>
          InsertResult Insert(TypeKey&& Key,T_Arg&&... Args){
            auto res=tree.Insert(std::move(Key),std::forward<T_Arg>(Args)...);
            return MakeInsertResult(res.ll_node,res.ok);
          }
          template<typename T,typename T_Key=TypeKey>
          InsertResult Insert(T_Key&& Key,std::initializer_list<T>&& initializer_list){return Insert(std::forward<T_Key>(Key),initializer_list);}

          InsertResult Insert(const Item& item){return Insert(item.Key(),item.Data());}


          TypeData& operator[](const TypeKey& Key){
            static_assert(std::is_default_constructible_v<TypeData>);
            return *Node::ToData(static_cast<Node*>(tree.Insert(Key).ll_node));
          }
          TypeData& operator[](TypeKey&& Key){
            static_assert(std::is_default_constructible_v<TypeData>);
            return *Node::ToData(static_cast<Node*>(tree.Insert(std::move(Key)).ll_node));
          }


          Iterator Find(const TypeKey& Key)noexcept{
            return Iterator(tree.FindNode(Key));
          }
          ConstIterator Find(const TypeKey& Key)const noexcept{
            return ConstIterator(tree.FindNode(Key));
          }


          RemoveResult Remove(const TypeKey& Key)noexcept{
            return RemoveResult(tree.Remove(Key));
          }

          bool Erase(const TypeKey& Key)noexcept{
            return tree.Erase(Key);
          }

          void Clear()noexcept{
            tree.ClearAll();
          }


          void Merge(TreeBase& treeBase)noexcept{tree.Merge(treeBase.tree);}


          Iterator begin()noexcept{return Iterator(tree.ForwardBegin());}
          Iterator end()noexcept{return Iterator(nullptr);}
          ConstIterator begin()const noexcept{return ConstIterator(tree.ForwardBegin());}
          ConstIterator end()const noexcept{return ConstIterator(nullptr);}

          Reverse_Iterator rbegin()noexcept{return Reverse_Iterator(tree.BackwardBegin());}
          Reverse_Iterator rend()noexcept{return Reverse_Iterator(nullptr);}
          Reverse_ConstIterator rbegin()const noexcept{return Reverse_ConstIterator(tree.BackwardBegin());}
          Reverse_ConstIterator rend()const noexcept{return Reverse_ConstIterator(nullptr);}

        private:
          Tree tree;
      };

    }

  }

}


#endif //hTree_H_Tree_HPP_
